package 中等.栈;

/**
 * 给你一个由 '('、')' 和小写字母组成的字符串 s。
 * 你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
 * 请返回任意一个合法字符串。
 * 有效「括号字符串」应当符合以下 任意一条 要求：
 * 空字符串或只包含小写字母的字符串
 * 可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
 * 可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-remove-to-make-valid-parentheses
 */
public class 移除无效的括号_1249 {

    public static void main(String[] args) {

        System.out.println(minRemoveToMakeValid("))(("));

    }

    /**
     * 用一个变量记录左括号的数量，如果碰到右括号，并且左括号数量为 0 时，
     * 需要删除这个右括号
     * 最后剩下 > 0 的左括号数量，也是需要删除的，从字符串右侧开始扫描，
     * 去除对应数量的左括号
     *
     * @param s
     * @return
     */
    public static String minRemoveToMakeValid(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        int leftCount = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') {
                leftCount++;
                stringBuilder.append(c);
            } else if (c == ')') {
                if (leftCount > 0) {
                    leftCount--;
                    stringBuilder.append(c);
                }
            } else {
                stringBuilder.append(c);
            }
        }

        while (leftCount-- > 0) {
            for (int i = stringBuilder.length() - 1; i >= 0; i--) {
                if (stringBuilder.charAt(i) == '(') {
                    stringBuilder = stringBuilder.delete(i, i + 1);
                    break;
                }
            }
        }

        return stringBuilder.toString();
    }

}
